/*
 * @Author: szx
 * @Date: 2021-10-28 10:36:44
 * @LastEditTime: 2021-10-28 19:41:00
 * @Description:
 * @FilePath: \leetcode\869\869.cpp
 */
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;
class Solution {
   public:
    bool reorderedPowerOf2(int n) {
        // 艹，居然还有这种函数
        string nums = to_string(n);

        sort(nums.begin(), nums.end());
        return backtrace(nums, 0, 0);
    }

    bool backtrace(string &nums, int start, int num) {
        // cout << start << " " << nums.length() << endl;
        if (start >= nums.length()) {
            cout << num<< endl;
            return isPowerOfTwo(num);
        }
        for (int i = start; i < nums.size(); i++) {
            if (num == 0 && nums[i] == 0) {
                continue;
            }
            int j = i - 1;
            while (j >= start && nums[j] != nums[i]) --j;
            if (j != start - 1) continue;
            swap(nums[start], nums[i]);
            if (backtrace(nums, start + 1, num * 10 + nums[i] - '0')) {
                return true;
            }
            swap(nums[start], nums[i]);
        }
        return false;
    }
    bool isPowerOfTwo(int n) { return (n & (n - 1)) == 0; }
};

// class Solution {
//    public:
//     bool reorderedPowerOf2(int N) {
//         string str = to_string(N);
//         sort(str.begin(), str.end());
//         for (int i = 0; i < 31; ++i) {
//             string t = to_string(1 << i);
//             sort(t.begin(), t.end());
//             if (t == str) return true;
//         }
//         return false;
//     }
// };

// class Solution {
//    public:
//     unordered_set<string> powerOf2Digits;
//     bool reorderedPowerOf2(int n) {
//         init();
//         return powerOf2Digits.count(countDigits(n));
//     }
//     void init() {
//         for (int n = 1; n <= 1e9; n <<= 1) {
//             powerOf2Digits.insert(countDigits(n));
//         }
//     }
//     string countDigits(int n) {
//         string cnt(10, 0);
//         while (n) {
//             ++cnt[n % 10];
//             n /= 10;
//         }
//         return cnt;
//     }
// };

int main() {
    Solution s;
    cout << s.reorderedPowerOf2(64) << endl;
    return 0;
}